/*
 * @lc app=leetcode.cn id=219 lang=cpp
 *
 * [219] 存在重复元素 II
 */

#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <limits.h>
using namespace std;

// @lc code=start
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        // 定义快慢指针，快指针比慢指针快 k 个元素
        int slow = 0;
        int fast = k;
        set<int> numbers;
 
        // 如果取值范围超过了数组元素数量
        if (k > nums.size() - 1) {
            for (int i = 0; i < nums.size(); i++) {
                if (numbers.count(nums[i]) == 0) {
                    numbers.insert(nums[i]);
                } else {
                    return true;
                }
            }
            return false;
        }

        // 增加头部元素
        for (fast = 0; fast <= k; fast++) {
            if (numbers.count(nums[fast]) == 0) {
                numbers.insert(nums[fast]);
            } else {
                return true;
            }
        }
        
        // 增加后续元素
        for (fast = k + 1; fast < nums.size(); fast++) {
            numbers.erase(nums[slow]);
            slow++;
            if (numbers.count(nums[fast]) == 0) {
                numbers.insert(nums[fast]);
            } else {
                return true;
            }
        }
        
        return false;
    }
};
// @lc code=end

